1. Field of the Invention
The present invention relates, in general, to performing proximity detection for computer simulations on parallel processing architectures, and in particular, for detecting the proximity of moving objects in a logically correct parallel discrete-event simulation.
2. Related Art
Providing proximity detection for simulations involving moving objects can be critical, especially when object interactions are restricted to finite ranges. Various parallel simulation studies in the past, such as "toy" simulations, have touched on the subject of proximity detection. These "toy" simulations ranged from colliding pucks to swimming sharks devouring nearby fish. However, "toy" simulations are not the only applications that require proximity detection. For example, interactive simulations, virtual reality, colliding space debris, biological models, and the modeling of interacting particles with short range forces are all real-world applications that require proximity detection.
In addition, proximity detection is also applied in the military community to confederate simulation elements by using the Distributed Interactive Simulation (DIS) set of protocols. Nevertheless, the DIS approach is not a logically correct simulation strategy because it uses the wall clock for synchronization. Events in a DIS exercise are therefore not repeatable. Protocol Data Unit (PDU) messages are broadcast and received by different DIS "cells" without regard for rigorous time ordering. Because DIS protocols were designed for real time training and systems acquisition decisions, the rigorous synchronization required for analytic studies is not as critical.
DIS uses a "dead reckoning" technique for simulation objects to compute the locations of other objects in their virtual world. DIS objects periodically broadcast their state information, which includes parameters for their dead-reckoning equations, to all of the other objects in the simulation. As a result, if there are N objects in the simulation, a total of N messages would be required, ie., one from each object. Each object must process and store the N messages resulting in a loss of scalability.
Objects broadcast their state information when either five real-time seconds have elapsed since the last broadcast or when the object has determined that the dead reckoning system, computed by the other DIS cells, is in error. Errors in the dead reckoning system arise when an object changes its equations of motion (EOM), or if cumulative errors in the dead reckoning system have exceeded a certain threshold.
Both conditions are motivated by the use of an unreliable "User Datagram Protocol" (UDP) for message communication and for providing interoperability. Consequently, DIS objects broadcast their state more frequently than what would have been required by strict adherence to discrete-event simulation practices. However, DIS is not technically a true synchronized discrete-event protocol.
Thus, the DIS strategy assumes that the perception envelope of each sensor includes the entire virtual world. Each sensor receives information about all moving objects continually during the simulation. The algorithms within the computer image generators that are connected to each sensor determine which objects in the virtual world are to be rendered or ignored.
A second example illustrating methods for proximity detection is the Concurrent Theater Level Simulation (CTLS) implemented under the Time warp Operating System (TWOS). In the initial approach of this system, the battlefield was decomposed into grids that represented physical regions of space. Although the scalar speed of the objects and their direction of motion could be changed at any time, objects were constrained to move in straight lines. Also, because all motion was modeled as a sequence of straight-line segments, only one type of EOM was needed. Thus, curved trajectories, for example, could be approximated only through a set of straight lines.
Combining the straight-line motion with a rectangular battle space grid boundary crossings is easily computed. If a mover changed its motion by either changing its speed or direction, grid crossing events that were erroneously scheduled were canceled through user cancellation messages. The actual proximity detection computations were performed by the grid objects themselves, which reduced overall message traffic. As a result, consistency in the treatment of proximity detection is ensured and the work from the moving objects is reduced.
However, it was not anticipated that military simulations would tend to behave like football games, where the player with the ball is chased. In a typical CTLS simulation run, most of the ground units would inevitably congest into a small number of grids to fight their battle. Because grids performed most of the work, they became bottlenecks, thus limiting the amount of parallelism in the simulation.
Consequently, proximity detection for simulations involving moving objects can be critical, especially when object interactions are restricted to a finite range. Hence, the goal of proximity detection is to provide correct spatial information for moving objects and participating sensor objects.
However, one of the fundamental and most difficult problems in supporting parallel simulations for military applications is providing proximity detection that does not bog down the simulation. The typical system currently utilized is dependent solely on the wall clock for synchronization, but this system is not logically synchronized and limits the repeatability of the simulation on parallel processing computers. Also, proximity detection must provide each participating sensing object with a list of equations of motion (EOM) for all other objects within its sensor range. This list must be correct at all simulation times.
Therefore, what is needed is a system that reduces or eliminates bottlenecks in the proximity detection simulation. What is also needed is a system that virtually eliminates instabilities by further reducing the number of messages required. What is also needed is a system that allows unrelated grid events to be processed out of order.
What is additionally needed is a system that can provide correct spatial information for moving objects. What is additionally needed is generalized proximity detection for moving objects in a logically correct parallel discrete-event simulation. What is further needed is a system for determining the views of each object in a manner that is fully scalable in terms of CPU usage, number of messages, and memory requirements.
Whatever the merits of the above mentioned existing systems and methods, they do not achieve the benefits of the present invention.